This invention relates to the selection of a first node which may be a file and references to that first node and the display of the first node and its references. This invention relates to address generation such as found on internet domain name servers. This invention relates to the display and navigation of context lists and relationships between contexts. This invention relates to hypergraph viewing and navigation.
FIG. 1 illustrates a prior art computer comprising one or more enclosures 10, housing a display device 12, selector device 14, and communication 16 between selector device and system, keyboard 20 and communication 22 between keyboard and system as well as door 24 for removable media. Enclosure 10 is shown herein with minimal detail by way of illustration. In practice, prior art system enclosures 10 relevant to this invention include but are not limited to television-style cases, desktop computer enclosures, notebook computer enclosures, hand held computer enclosures and rack-mounted computer enclosures. Many of these enclosures 10 incorporate speakers with them, in some instances, being perceived separate from the enclosure 10. Note that there are a number of systems containing more than one enclosure 10, as illustrated, such as a number of desktop computers, televisions with set top boxes and often, additional removable media interfaces such as DVD players. Prior art servers are often rack-mounted and in many circumstances, possess minimal display device 12, selector device 14 and keyboard 20 capabilities. Such minimal display device 12, selector device 14 and keyboard 20 capabilities may for instance be shared between several servers mounted in one rack.
Relevant prior art display devices 12 are also widely varied in form and specifics of operation. Relevant prior art display devices 12 may present black and white or color images. Relevant prior art display devices 12 may support either a vector or raster format. Relevant prior art display devices 12 may present images in either a 2-D, 3-D or multi-dimensional presentation view or collection of views.
Relevant embodiments of selector device 14 include but are not limited to contemporary television channel selectors, home entertainment center remote controls, computer pointing devices including but not limited to 3-D and 2-D mouse-style pointers, pen tablets, track balls, touch pads, key pads and joysticks. As illustrated in FIG. 1, the selector device communicates via physical transport mechanism 16 with an interface housed in enclosure 10. Relevant physical transport mechanisms 16 include but are not limited to infra-red, micro-wave and other similar wireless transport layers, as well as wires and optical fiber. The mechanism by which communication is carried out based upon the specific physical transport mechanism employed is not relevant to this invention and will not be discussed for that reason.
Keyboards 20 may be attached to various relevant, prior art systems. Keyboards 20 may house touch pads and mouse sticks which in certain cases are the relevant selector device 14 of that system.
FIG. 2 displays a system block diagram of a prior art computer. The units (12, 14, 20 and 54) on the left side and bottom of this figure all have a major role in the input and output flows processed and are controlled by the second column of units (46, 38, 42 and 58), respectively. The data transport mechanisms between units (12, 14, 20 and 54) and units (46, 38, 42 and 58) are represented by arrows (52, 16, 22 and 56), respectively. These units interact with each other and an overall control circuit labeled digital controller 50 via arrows representing buses (48, 44, 40, 60). Additionally, units 30 and 34 interact with digital controller 50 as represented by arrows 32 and 36, respectively. Digital controller 50 in turn has RAM and Nonvolatile memory, which it controls and uses to direct the overall operation of relevant prior art systems via buses.
Relevant prior art display devices 12 may present black and white or color images in either a vector or raster format representing images in either a 2-D, 3-D or multi-dimensional presentation view or collection of views. Relevant display data transport 52 includes but is not limited to NTSC, PAL or various HDTV television protocols of either analog or digital formats, as well as digital and analog RGB and various flat panel display interface protocols as are often used with computer displays. Many systems today possess a specialized display interface 46, which often incorporates one or more temporary frame buffers and MPEG decoding acceleration technology as well as acceleration technology for a variety of graphics operation. The communication mechanism 48 by which these units interact with the rest of an exemplary prior art system include but are not limited to microcomputer busses such as PCI and AGP as well as dedicated communication paths. Display devices 12 comprise traditional display devices and force feedback tactile and auditory display devices.
The selector device 14, selector device communication mechanism 16 and selector interface 38 have been discussed above. The communication between the selector interface 38 and the rest of the system is denoted by arrow 44. Embodiments of arrow 44 include but are not limited to addressable interfaces on computer busses including but not limited to ISA, PCI and USB.
Relevant, prior art removable media interface 34 embodiments include but are not limited to optical disk players and electromagnetic disk players of a removable media. These removable media interfaces 34 embodiments further include but are not limited to CD ROM, MPEG and DVD players. Such removable media interface 34 embodiments may further include the ability to write to the storage media as well as play the storage media. Relevant removable media interface 34 embodiments include but are not limited to various SCSI controllers, specialized optical disk controllers, specialized hard disk controllers and RAID disk array controllers. Removable media interface 34 embodiments may further include but are not limited to various continuous play media compression decoders: MPEG decoders and DVD decoders. Relevant prior art communications mechanisms 36 include but are not limited to various SCSI, RAID, ISA and EISA interfaces.
Note that in relevant prior art systems, there may be more than one, potentially distinct, removable media interface 34 with potentially distinct interfaces and communication paths 36. One removable media interface 34 might support a writeable CD ROM using a SCSI controller as well as a second DVD-ROM player with its own cabling and player interface 34.
Additionally mass storage 30 with communication coupling to digital controller 50 represented by arrow 32 may possess a similar range of operational characteristics: Mass storage 30 embodiments often possess a file management system afforded by operating systems such as UNIX, LINUX, Microsoft Windows™, MacOS™, among others. Mass storage 30 embodiments include but are not limited various electro-magnetically encoded media as well optically encoded media. Mass storage 30 embodiments include but are not limited read-only, plus write-once and read often and read-write media. Mass storage 30 embodiments include but are not limited to various SCSI controllers, specialized optical disk controllers, specialized hard disk controllers and RAID disk array controllers. Removable media interface 34 embodiments may further include but are not limited to various continuous play media compression decoders: MPEG decoders and DVD decoders. Relevant prior art communications mechanisms 32 include but are not limited to various SCSI, RAID, ISA and EISA interfaces.
Another relevant source of continuous play media content is provided via external environment 54 communicating with external interface 58 via arrow 56. One relevant external interface 58 is a radio frequency (RF) tuner. Relevant RF tuners 58 include but are not limited to demodulators and/or modulators for various broadcast protocols such as Frequency Modulation (FM), Frequency Division Multiple Access (FDMA), Time Division Multiple Access (TDMA), various spread spectrum protocols, Wavelength Division Multiple Access and wavelet division multiple access. Relevant spread spectrum protocols further include but are not limited to Direct Sequence, Frequency Hopping, Time Hopping and Wideband CDMA. These relevant RF tuners may be connected 56 by wireline or wireless physical transport layers. Relevant wireline physical transports include but are limited to twisted pair, coaxial cable and various optical fiber mechanisms. Relevant wireless physical transports 56 include contemporary broadcast television, High Definition TV (HDTV), as well as various radio frequency, microwave and infra red schemes which may well incorporate an antenna, sensor or array of antennas or sensors.
Another relevant external interface 58 is a modem. Relevant modems include but are not limited to telephone line modems incorporating various transceiver rates which may not be the same for reception as for transmission, as well as various DSL, ADSL, XDSL, ISBN, Ethernet, Token Ring and ATM interfaces. Physical transport layer 56 for modems include but are not limited to wire line and wireless transport layers. Wire line physical transport layers 56 include but are not limited to telephone lines, twisted pair wire lines, coaxial cabling and various optical fiber technologies. Wireless transport layers 56 include but are not limited to directional and non-directional radio, microwave, infrared and optical schemes.
The external environment 54 may be physically located a substantial distance away from the enclosure 10. The external environment 54 is often embodied in many circumstances within a server supporting a network of user systems via interconnections 56 of these external interfaces 58. Such networks may well support TCP/IP thereby enabling support for the Internet. Such networks may further support one or more Intranets. Such networks may further support one or more Extranets.
Note that in many relevant prior art systems, there is more than one kind of external environment 54 and external interface 58 with potentially different communication paths 56. A settop box might possess both a RF tuner using an antenna as well as an optical fiber interface to a cable television provider. A notebook computer might well have both a telephone line modem and an Ethernet LAN interface.
Relevant prior art digital controller 50 embodiments include but are not limited to one or more of the following: general purpose microprocessors, Digital Signal Processors (DSPs), parallel processors, embedded controllers and special purpose system controllers. General purpose microprocessors include but are not limited to various word width Complex Instruction Set Computers (CISC) and Reduced Instruction Set Computers (RISC). DSPs include but are not limited to various word width computers employing instruction sets allowing at least one add/subtract operation as well as at least one operation comparable to multiplication to be performed in a single instruction cycle. Parallel processors include but are not limited to Single Instruction Multiple Datapath (SIMD), Multiple Instruction Multiple Datapath (MIMD), and hybrid SIMD/MIMD organizations of either uniform or non-uniform processors. Uniform processor parallel processors employ essentially the same processor uniformly. Non-uniform processor parallel processors do not employ essentially the same processor throughout. Embedded controllers often incorporate either one or more microprocessors or DSPs along with additional circuitry performing specialized data processing, which may include but is not limited to MPEG stream partitioning and/or decoding, copy protection processing, decryption, authentication and block data error detection and correction. Special purpose system controllers include but are not limited to various implementations as Programmable Logic Arrays (PLAs), Complex Programmable Logic Devices (CPLDs), Field Programmable Gate Arrays (FPGAs), Application Specific Integrated Circuits (ASICs) and Application Specific Standard Products (ASSPs).
Relevant prior art digital controllers 50 often possess local memory resources in the form of RAM and nonvolatile memory, interfaced via busses. The RAM may include but is not limited to various forms of RAM and one or more caching banks of RAM. Relevant prior art digital controller 50 embodiments may include but are not limited to one or more of memory caches physically proximate to and possibly contained within the digital controller 50 package or packages. Memory caching may include but is not limited to separate caching of memory and data. Memory caching may further include but is not limited to multiple layers of cache structures. Distinct processors within the digital controller 50 may further possess distinct caches as well as further localized memory which may in turn include RAM and/or nonvolatile memory. Relevant prior art nonvolatile memory may include but is not limited to boot ROMs and flash memory circuits which may further emulate disk drives with a form of file management system. Such nonvolatile memory embodiments may be used to initialize the system as well as provide security and accounting information or store content.
FIG. 3 displays a prior art file system configuration showing references as hard aliases of a node 114. In such configurations, there is an assumption of a root 100 for the file system. Arrows 102, 104 and 106 indicate directory paths to file folders 108, 110 and 112, respectively. File folders 108, 110 and 112 in turn contain nodes 114, 126 and 132, respectively. Node 114 includes 122 file 116 further including content 120, which is addressed by the file management system as 118, specifying a path and filename as “Path1/file1”. Note that in many file management systems, 122 is a data structure known variously as a descriptor. Node 126 has a descriptor 128, which is a soft alias to node 114. Node 132 has a descriptor 134, which is a soft alias to node 114. Access of nodes 126 and/or 132 will be indirect accesses of node 114. When a node is accessed, the access immediately proceeds to the node 114, which accesses the file 116 and the path and filename at 126 or 132 is lost. This mechanism has been used extensively in UNIX-style file management systems. It has been used advantageously to develop extensive software systems such as compilers and VLSI simulation and Computer Aided Design tools and environments.
There is however a persistent problem in such systems: there is no commonly available mechanism by which someone can find all the references to a given node. This can lead to quite inconvenient situations when there is an unknown reference node causing problems in the software environment. By way of example, if there is an incorrect reference to a 3 input nand gate model, rather than a four input nand gate model in a behavioral simulation, it can be quite expensive to track down the faulty reference.
There is another problem inherent in this situation, which is subtle but which has wide-ranging consequences. To discuss the problem requires development of some terms and a look at part of the history of computing. A standard conceptual tool in computer science is the graph, by which is meant a total collection of “points” and a collection of “arcs”, each connecting a first point and a second point. A directed graph is a graph in which the arcs are arrows from a first point to a second point. In an undirected graph, an arc connecting point 1 to point 2 is the same as the same as an arc connecting point 2 to point 1. A path of a graph is an ordered collection of arcs 1, 2, . . . , An-1, An where the first point of 2 is the second point of 1, etc, till the first point of An is the second point of An-1. A graph has a cycle if there are two points possessing two distinct paths between those two points, or alternatively, there is a path where the first point of the first arc of the path is the second point of the last arc in the path. An acyclic graph is a graph containing no cycles. A graph is connected if for any two points of the graph, there is a path between those two points. A tree is a connected, acyclic graph. A tree can be seen as having a root point from which all other points in the tree are connected by arcs.
Computer science has found these terms to be extremely useful in providing a basic language about which to conceptualize a number of important mechanisms used in computing for years. File management systems have been consistently portrayed in operating systems such as UNIX, MSDOS (now Windows) and MacOS (which incorporates a form of UNIX) as hierarchical directory structures. These hierarchical directory structures are acyclic graphs, trees, proceeding from a specific root point (directory). This was and is a major feature of UNIX as well as MSDOS (now Windows) and MacOS. The problem with this hierarchical portrayal of file systems is that hard aliases often fail to conform with the model. Hard aliases essentially create cycles in the graph of a file system. Such a portrayal of a file system as a cyclic graph runs counter to the standard teachings on file management systems as seen in UNIX, MSDOS, Windows and MacOS. The discussion of FIG. 3 and the following prior art figures will document situations where users want to see their file structures in the above-mentioned operating systems in ways these operating systems do not even conceptually permit. A standard perspective on file systems (in particular, UNIX file systems) is to be found in “Chapter 2:The File System”, on pages 41-70, The UNIX Programming Environment, by Brian W. Kernighan and Rob Pike, © 1984 Bell Telephone Laboratories, Incorporated, published by Prentice-Hall, Inc.
FIG. 4 displays a prior art file system configuration showing references to soft aliases of a node 114. As in FIG. 1, there is an assumption of a root 100 for the file system. Arrows 102, 104 and 106 indicate directory paths to file folders 108, 110 and 112, respectively. File folders 108, 110 and 112 in turn contain nodes 114, 150 and 170, respectively. Node 114 includes file 116 further including through descriptor 122, content 120, which is addressed by the file management system as 118, specifying a path and filename as “Path1/file1”. Node 150 includes file 152 further including through descriptor 158, content 156, which is addressed by the file management system as 154, specifying a path and filename as “Path2/file2”. Node 170 includes file 172 further including through descriptor 178, content 176, which is addressed by the file management system as 174, specifying a path and filename as “Path3/file3”. Descriptors 158 and 178 act as soft aliases to node 114, essentially mirroring the contents at their respective locations in the file name system. The advantage this brings is the ability to retain the local path and file name at nodes 150 and 170.
The disadvantage is the difficulty discovering whether nodes 150 and 170 are the sources of their file contents, or aliases of it. The persistent problem discussed above also shows up in such system configurations: there is no commonly available mechanism by which someone can find all the soft and hard references to a given node 114. This can lead to quite inconvenient situations when there is an unknown reference node causing problems in the software environment. By way of example, if there is an incorrect reference to a 3 input nand gate model, rather than a four input nand gate model in a behavioral simulation, it can be quite expensive to track down the faulty reference.
Note that in this situation, we again encounter a cyclic graph, when the file management system is “supposed” to be a directory tree. File management systems have been consistently portrayed in operating systems such as UNIX, MSDOS (now Windows) and MacOS (which incorporates a form of UNIX) as hierarchical directory structures. These hierarchical directory structures are connected acyclic graphs, trees, each proceeding from a specific root point (directory). This was and is a major feature of UNIX as well as MSDOS (now Windows) and MacOS. The problem with this hierarchical portrayal of file systems is that soft aliases often fail to conform with the model. Soft aliases essentially create cycles in the graph of a file system. Such a portrayal of a file system as a cyclic graph runs counter to the standard teachings on file management systems as seen in UNIX, MSDOS, Windows and MacOS. The users again want to see their file structures in the above-mentioned operating systems in a manner these operating systems do not even conceptually permit.
FIG. 5 displays a prior art file system configuration showing references essentially containing the content of a node 114. As in FIG. 1, there is an assumption of a root 100 for the file system. Arrows 102, 104 and 106 indicate directory paths to file folders 108, 110 and 112, respectively. File folders 108, 110 and 112 in turn contain nodes 114, 190 and 210, respectively. Node 114 includes through descriptor 122 file 116 further including content 120, which is addressed by the file management system as 118, specifying a path and filename as “Path1/file1”. Node 190 includes file 192 further including through descriptor 198, content 196, which is addressed by the file management system as 194, specifying a path and filename as “Path2/file4”. Node 210 includes file 212 further including through descriptor 218, content 216, which is addressed by the file management system as 214, specifying a path and filename as “Path3/file5”.
In the portrayed situation, the content 120 is essentially contained in content 196, as well as the content 120 is essentially contained in content 216. In a first situation, content 120 is essentially copied as content 196. One example occurs when content 120 is exactly content 196. A file may have been exactly copied from a remote server to the local system in order to minimize network traffic. Such often happens in communication intensive software tasks, such as behavioral electronic simulations. In another exemplary situation, the content 120 is essentially the same as content 196. Consider that file 116 and file 192 may be word-processor versions of the same document, only differing in a type font setting. File 116 and file 192 may be graphics file versions of the same picture, only differing in a color scheme selection, such as differing shades of blue. In yet another exemplary situation, content 120 is essentially incorporated into the content 216. File 116 may be an earlier version of file 210. Alternatively, content 120 may have been used as a background in content 216. This often occurs in graphical applications: A view 120 has other objects superimposed upon it to create content 216. Additionally, content 120 may be clipped to a sub-image, which is then incorporated into a large image to create content 216. Such operations have been seen repeatedly in “clipping out” a face from a photo to incorporate it into a different background. Note that content 120 may alternatively be an audio sequence and content 210 may be an audio or audio-video sequence. Note that the above examples of image data include but are not limited to both still frame, motion video and integrated motion video and audio. In each of these situations, it is very difficult to create the collection of which nodes essentially reference node 114 with conventional tools.
Note that essential containment again often creates cyclic graphs traversing a file system. The cyclic graph is encountered, contradicting the file management system, which is “supposed” to be a directory tree. File management systems have been consistently portrayed in operating systems such as UNIX, MSDOS (now Windows) and MacOS (which incorporates a form of UNIX) as hierarchical directory structures. These hierarchical directory structures are connected acyclic graphs, trees, proceeding from a specific root point (directory). This was and is a major feature of UNIX as well as MSDOS (now Windows) and MacOS. The problem with this hierarchical portrayal of file systems is that hard aliases often fail to conform with the model. Hard aliases essentially create cycles in the graph of the file system. Such a portrayal of a file system as a cyclic graph runs counter to the standard teachings on file management systems as seen in UNIX, MSDOS, Windows and MacOS. The users want to see their file structures in the above-mentioned operating systems in a manner these operating systems do not even conceptually permit.
Another situation illustrating this involves the use of archive files. Archive files include but are not limited to files containing compressed versions of the content of other files. Often a library with the content of multiple files is to be found in an archive file. Archive file technology is often used to build intermediate versions of software program components prior to the linkage editor phase of program generations, as well as in the form of “dll” (Dynamic Link Libraries) in the Windows systems. Archive file technology is also used to compress information to be transmitted or placed on some form of portable media, such as floppy disk, CD ROM, etc. In such cases, there is a file which essentially contains the content of one or more other files, again causing arrows from one or more points throughout a file system directory tree to create cycles in the graph. In essence, people repeatedly break the acyclic graph-model of a hierarchical directory structure in the process of using their computers. It is a problem that the standard hierarchical file system model does not account for.
Archival files also reveal another subtle but very significant problem which requires development of some terminology. Hypergraphs are defined as a total collection of points and a collection of hyper-arcs. Each hyper-arc is composed of at least two points. By way of example, assume a first hyper-arc composed of PT1, PT2 and PT3; a second hyper-arc composed of PT2, PT3 and PT1. The first hyper-arc is essentially equal to the second hyper-arc. A directed hypergraph is a hypergraph in which each the points of each hyper-arc are ordered. Assume now that the point ordering of the first and second hyper-arc were as portrayed, then the first hyper-arc would not be essentially equal to the second hyper-arc in this example.
These terms, graphs, trees, acyclic graphs, cycle graphs and hypergraphs have been in use amongst parts of the mathematical and computing community since at least the 1910's and 1970's. Hypergraphs include graphs. There has been a consistent teaching toward trees, away from graphs in most instances, and very much away from hypergraphs. While hypergraphs are more general than graphs and trees, their discussion outside of limited portions of these communities has not been widespread, even though they provide the conceptual tools to unify at least the problems discussed above and those outlined in what follows.
A standard approach to graph algorithms in computer science is to be found in Graph Algorithms by Shimon Even, © 1979 Computer Science Press, Inc., ISBN 0-914894-21-8. A less common viewpoint regarding hypergraphs can be found in Combinatorics: set systems, hypergraphs, families of vectors and combinatorial probability, by Bela Bollobas, © 1986, Cambridge University Press, ISBN 0-521-33703-8. In this work, particularly the preface (pages xi-xii) and the notational introduction (pages 1-3), graphs are defined as specialized hypergraphs, and the tendency to minimize discussion hypergraphs is mentioned.
There is a further difficulty revealed in considering FIG. 5: consider the situation of copyrighted image material 120 being incorporated into other images. Assume that image material 120 possesses an embedded copyright signature. There are several software tools which embed copyright signatures into content material 120 immune to color changes and which survive the clipping out of relatively small pieces of the material 120, such as a face. However, there are no tools available which will construct a context list of nodes essentially referencing this material based upon detecting the copyright signature. Note that many creators of content must now resort to labor intensive mechanisms to search for copyright infringing material. In certain situations, paths 104 and 106 represent virtual paths in a distributed network such as the Internet. In certain situations, paths 104 and 106 represent paths on a removable media such as a CD ROM or DVD ROM. Note further that the content 120 may be still frame and content 210 may be motion video, or vice versa.
Note that in this situation, we again encounter a cyclic graph, when the file management system is “supposed” to be a directory tree. File management systems have been consistently portrayed in operating systems such as UNIX, MSDOS (now Windows) and MacOS (which incorporates a form of UNIX) as hierarchical directory structures. These hierarchical directory structures are acyclic graphs, trees, proceeding from a specific root point (directory). This was and is a major feature of UNIX as well as MSDOS (now Windows) and MacOS. The problem with this hierarchical portrayal of file systems is that soft aliases often fail to conform with the model. Soft aliases essentially create cycles in the graph of a file system. Such a portrayal of a file system as a cyclic graph runs counter to the standard teachings on file management systems as seen in UNIX, MSDOS, Windows and MacOS. The users want to see their file structures in the above-mentioned operating systems in a manner these operating systems do not even conceptually permit.
FIG. 6 displays a prior art file system configuration showing references to a revision controlled source 222. As in FIG. 1, there is an assumption of a root 100 for the file system. Arrows 102, 104 and 106 indicate directory paths to file folders 108, 110 and 112, respectively. File folders 108, 110 and 112 in turn contain nodes 230, 250 and 270, respectively. Node 230 includes file 232 further including through descriptor 238, content 236, which is addressed by the file management system as 234, specifying a path and filename as “Path1/file b”. Node 250 includes file 252 further including through descriptor 258, content 256, which is addressed by the file management system as 254, specifying a path and filename as “Path2/file 7”. Node 270 includes file 272 further including through descriptor 278, content 276, which is addressed by the file management system as 274, specifying a path and filename as “Path3/file 8”.
In these configurations, there is a separate source of content at node 222, coupled to the regular file management system as indicated by arrow 224. Content 236, 256 and 276 is essentially maintained from node 222. Changing the contents of node 222 will automatically force the propagation of those changes to nodes 230, 250 and 270. The advantage here is that one can update the contents of these representations by modifying just one node. The persistent problem is determining from a node such as 230, which are the other nodes referencing the same content, and where the source of that content may be found.
Note that in this situation, we again encounter a cyclic graph, when the file management system is “supposed” to be a directory tree. File management systems have been consistently portrayed in operating systems such as UNIX, MSDOS (now Windows) and MacOS (which incorporates a form of UNIX) as hierarchical directory structures. These hierarchical directory structures are acyclic graphs, trees, proceeding from a specific root point (directory). This was and is a major feature of UNIX as well as MSDOS (now Windows) and MacOS. The problem with this hierarchical portrayal of file systems is that soft aliases often fail to conform with the model. Soft aliases essentially create cycles in the graph of a file system. Such a portrayal of a file system as a cyclic graph runs counter to the standard teachings on file management systems as seen in UNIX, MSDOS, Windows and MacOS. The users want to see their file structures in the above-mentioned operating systems in a manner these operating systems do not even conceptually permit.
FIG. 7 displays a prior art domain name lookup table 300. A particular server domain has exactly one entry in such a table, represented as a row. Each row is composed of component entries labeled by way of example as second level 302, first level 304, and URL 306 as shown in row 300. Each server has a unique URL composed of 4 numbers separated by periods. Each of these four numbers ranges from 0 to 255. Each URL may further have a 16 bit unsigned decimal integer associated with it, called a port address. The URL port numbers have not been shown to simplify the discussion. Each level of the domain name is a collection of characters, usually alpha-numeric which follow a set of additional syntactic rules (which are not the subject of this invention, and will be left silent to simplify the discussion). A specific domain name, such as “acme.com” could then be represented by a row of entries 310, where “acme” is the second level entry 312, “com” is the first level entry 314, and “1.2.3.141” is the URL entry 316. A second domain name, such as “monkey.com” could then be represented by a row of entries 320, where “monkey” is the second level entry 322, “com” is the first level entry 324, and “101.11.23.121” is the URL entry 326. A third domain name, such as “uspto.gov” could then be represented by a row of entries 330, where “uspto” is the second level entry 332, “gov” is the first level entry 334, and “121.101.1.5” is the URL entry 336.
This system has proven itself to be of exemplary utility, supporting an unprecedented increase in communication throughout the world. The four component URL numbering scheme can support addressing up to 4 billion servers, which is almost as many servers as there are people in the world. With the additional 16 bit port addressing, the use of firewalls, etc. there is enough addressing space to accommodate service for many years to come. There are however, some uncomfortable issues regarding this scheme. There can be only one “acme.com”, but there are numerous acme companies in the United States. Similarly, suppose several families named “Smith” each want their own web-site. There is no readily available mechanism by which these name usage collisions can be effectively sorted out. While in general Internet and the World Wide Web have proven themselves to be quite open to experimental changes, this is one area where this is not true.
FIG. 8A displays a prior art search engine interface. Such search engines are found in web sites such as the US PTO patent database, on CD ROM product catalogs and datasheets, as well as many other environments. The details vary widely, but the overall discussion and basic features described herein or variants thereof are found in these applications. There are often two components, a search command component 340 and a search result component 350. The search command component 340 possesses a first command component 342, with an optional operator component 344 and optional command component 346. There are often additional controls to reinitialize the search buffer, start the search, cancel the search, as well as possibly other controls. Once the search has been performed the search result component 350 may contain one or more referencing nodes as illustrated by boxes 352, 354, 356 and 358. Each of these boxes may have some form of salience metric associated with the match performed in accordance with the search command(s) of the search command component 340.
Salience is a term used hereinafter. In a number of circumstances, such as web-based searches, the term is related to “relevance” metrics. These forms of salience metrics are often based upon frequency of which a word or phrase is found in a document. Salience metrics can represent a sense of distance between two such words or phrases, or how close such a word or phrase is to the beginning of a web page document.
This relatively simple interface has been a breakthrough for locating information in the ever-increasing complexity of our times. It has helped people, without ever leaving their home or office, to find and retrieve information from widely diverse sources all over the world in a small fraction of the time it previously took to just get to the local library. Its operation can be frustrating. A search for common name or surname may return thousands of entries, often with little or no obvious way to reduce the number of results in a coherent fashion.
There is a further problem inherent in existing, user friendly interfaces to databases. Salience metrics in a database context can refer to measure of satisfaction of some relationship. Consider a financial database, by way of example. A first relationship in the financial database may be the percentage of income paid for state taxes of a given state by a taxable entity. A second relationship may be the percentage of income paid for national taxes by a taxable entity. A third relationship may be the amount of state income tax to be paid by a taxable entity. A fourth relationship may be the amount of national income tax to be paid by a taxable entity. A fifth relationship may be the age and filing status by the taxable entity. A reasonable query of such a database might well include a specific range of percentage state income tax, a specific range of amounts of state income tax and a specific percentage national income tax for a specific combination of age and small business entity.
Such flexible and complex queries are possible with computer programming tools such as Visual Basic, C, C++ and COBOL, to name just a few of the many languages used in such tasks. However, such tools are outside the range of convenience most users of computers can and will tolerate. Further, there is a significant effort necessary to learn such tools and then to debug such programmed interfaces. What is needed is a flexible user interface, which allows the user to perform such queries in a more humanly efficient and painless fashion.
There is an additional, though subtle problem inherent in the standard teachings regarding the portrayal of data in databases. Consider part of the data structure of a patent in the Patent and Trademark Office's patent database. Each patent incorporates a patent number, issue date, filing date, its parentage in terms of being a continuation, divisional, continuation-in-part of a previously filed U.S. patent, which is referenced by its patent number, as well as the inventor list, possibly an assignee, primary examiner and a classification search list. Such an entity is best seen as a hypergraph embedded in a larger hypergraph, such as the database in its entirety or all patents issued on a given day.
Relationships involving multiple attributes, which operations upon many databases often require are not accessible through a graph paradigm. The context of such relationship is often an ordered n-tuple of attributes, where n is often greater than 2. A hyper-arc composed of n ordered attributes is a natural way to portray the entities upon which such relationships act.
The evolution of relationships in computer science and mathematical logic can be seen in considering the definition of relation found on pages 138-139 of The elements of mathematical logic, by Paul Rosenbloom, © 1950 Dover Publications, Inc. The definition is of a subset of a Cartesian cross product of a set with itself. Such a definition was sufficient to handle comparison relationships such as =, > and < as required for integer arithmetic. By the late 1960's and early 1970's, a much more sophisticated definition can be seen on page 11 of Saturated Model Theory, by Gerald E. Sachs, © 1972 W. A. Benjamin, Inc. ISBN 0-805-38380-8. In this definition, a relationship operates on an n-dimensional cross product of potentially different sets. Such a definition is capable of describing the relationships involved in many database activities, although that capability is silent in the text. The interaction between databases and logic matures by the late 1970's, in part due to the development of logic programming languages such as Prolog. This can be seen by examining “Chapter 1: Introduction”, pages 1-21, Logic for Problem Solving, by Robert Kowalski, © 1979, Elsevier Science Publishing Co., Inc. 3rd printing, 1983 (paperback), ISBN 0-444-00368-1. Note that relationships are acting on elements of these n-dimensional cross products of potentially different sets. Further note the discussion is focused exclusively on graphs and trees. There is no way to visualize these relationships as geometric entities. This limitation persists to this day.
FIG. 8B displays a prior art graph based content viewer 360 containing a content viewing component 362 and a graph viewing/navigation component 364. An acyclic graph is displayed in region 364 composed of points 366, 370, 374, 376, 378, 380, 382, 384 and 386, as well as arcs 368, 372, 377, 379, 381, 383, 385, and 390 connecting pairs of these points. Each point is associated with content, which when the point is selected, is displayed in region 362. In certain prior art systems, the portrayal of the graph in region 364 provides more detail to the nearest-graph neighboring points and arcs using an approach known as a “fish-eye” or hyperbolic view. These content viewers have been seen in embodiments out of Xerox PARC such as the hyperbolic browser and visual thesaurus. In each case, the content viewer is presented with an acyclic graph with each point associated with content, such as displayed in this figure. Further, these prior art viewers require an acyclic graph. These viewers teach away from the portrayal of graphs with cycles, much less hypergraphs. This can be seen by examining the document “A Focus+Context Technique Based on Hyperbolic Geometry for Visualizing Large Hierarchies.” By John Lamping, Ramana Rao and Peter Pirolli, © ACM, found on Jan. 11, 1999 at the following web-address:
http://www.acm.org/sigchi/chi95/proceedings/papers/jl_bdy.html.
FIG. 9 displays a prior art file manager user interface 400. In this example, the interface is composed of a directory tree view 402, a file list viewer 404, and a file snapshot viewer 406. The file list viewer 404, shows the content a currently selected node in the file directory structure as viewed in 402. Directory tree viewers 402 typically represent a node as a horizontal component in the display. By way of example, the root of the directory tree being viewed is denoted by the items 410, 412 and 414. Item 410 shows that this node is a directory with file contents through the symbol “+” in the center of the box. Item 414 displays the node name, in this case “ROOT”. Item 416 indicates the extent of containment of the node “ROOT”. Items 420, 422, 424 and 426 indicate the node “Speeches”, which is a sub-directory under “ROOT”. Items 430, 432, 434 and 436 indicate a specific file named “Gettysburg.doc”, which is contained in “Speeches”, which is further contained in “ROOT”. Items 440, 442, 444 and 446 indicate a specific file named “I have a dream.doc”, which is contained in “Speeches”, which is further contained in “ROOT”. Note that the filename has been truncated here, in comparison to its representation in 404. Items 450, 452, 454 and 456 indicate an unnamed node, which is a sub-directory under “ROOT”. Items 460, 462, 464 and 456 indicate a specific unnamed file, which is contained in directory 456 which is further contained in “ROOT”. Items 470, 472, 474 and 476 indicate a specific unnamed file, which is contained in 456, which is further contained in “ROOT”. In this example, the node 426 is selected, which contains files “GETTSYBURG.DOC” and “IHAVEADREAM.DOC”. These two files are shown in the file list viewer 404 as 436 and 446. These same files are represented in the directory tree viewer 402 as 436 and 446. The user has further selected “GETTSYBURG.DOC” 436, so that file snapshot viewer 406 shows “Four Score and seven years ago, . . .”, which is the start of that speech.
This user interface is in widespread application in all of the operating systems mentioned above, in applications such as word processing, spreadsheets, integrated development environments for software, electronics design and image processing. It has however, a consistent frustration for users. Such user interfaces cannot reveal which nodes essentially reference a given node. This regularly leads to a large amount of effort being needed to track down the references by hand. Note again that the operating system paradigm of a hierarchical directory structure, with its directory tree does not conceptually permit cycle graphs, where the cycles are formed from files essentially referenced by other files.
The frustration has only grown in significance as time has passed. Today there is a major effort underway by providers of creative content such as pictures, music, motion videos, etc. to uphold copyright protection. This has lead to the development of copyright signature embedding mechanisms for visual data, such as still frames. Determining if a node of content has been essentially incorporated into another content becomes the task of finding the copyright signature. The task of automatically searching a tree of nodes becomes that much more significant.
The issue of essential containment, whether through incorporation of an image modified from its node of origin, or a file compressed and incorporated into a larger file, again opens the user to thinking in terms of hypergraphs. And again, the operating systems and the standard user interface paradigm of a hierarchical file directory system expressed consistently as a directory tree teaches away and discourages such thoughts.
FIG. 10 displays a prior art file manager user interface seen as a web page 480. Such interfaces are found on all of the operating systems mentioned above. They are often composed of a path and filename designating box 482. They also contain a region 484 which displays the contents of the node whose path and filename are represented in box 482. By way of example, four items are shown contained in this node, 486, 488, 490 and 492. Items 486, 488 and 490 are shown as similarly shaped icons. Note that in most of these interfaces, there must be some visibly distinguishing characteristic to identify these items as separate nodes. Item 492 is shown as a different icon. Note that icons may further incorporate a text label as shown with item 494, which is associated with item 492. Item 492s is shown as an icon commonly used to designate a sub-directory of the current node.
This user interface is found in all the above-mentioned operating systems and in many applications. It also has a consistent frustration for users. Such user interfaces cannot reveal which nodes essentially reference a given node. This regularly leads to a large amount of effort being needed to track down the references by hand.
The frustration similarly has only grown in significance as time has passed. Today there is a major effort underway by providers of creative content such as pictures, music, motion videos, etc. to uphold copyright protection. This has lead to the development of copyright signature embedding mechanisms for visual data, such as still frames. Determining if a node of content has been essentially incorporated into another content becomes the task of finding the copyright signature. The task of automatically searching a tree of nodes becomes that much more significant.
Note again that the paradigm of a directory tree structure runs counter to what these users are trying to do. These essentially referenced files effectively create cycles in the file system graph from the user's standpoint. These operating systems (UNIX, MSDOS, Windows and MacOS) teach away from these cyclic graph structures.
Essential references based upon “essentially being contained”, open the door to the user thinking in terms of hypergraphs, where the essentially containing files represent the hyper-arcs and the points of the hypergraph are the files essentially referenced. Note that this is again something these very common operating systems do not conceptually permit.
FIG. 11 displays a prior art web browser 500. What is displayed is a fairly typical view of hypertext content found at a web-site address shown in 502. There has been no portrayal of the numerous other features of these interfaces, such as menu bars, because they are not central to this discussion. For the sake of uniformity of exposition, various web-sites will be composed of nodes, such as their home page. The node viewer 504 shows a combination of hyperlinks to other nodes 508, 512, and 514. Node viewer 504 also contains text lines 510 and image data 506. Image data 506 may be still frame or change over time. Text data, which is displayed, such as contained in html files, will be considered image data hereinafter. Image data, which changes over time, will be considered motion video hereinafter.
This user interface is in widespread application in all of the operating systems mentioned above. It also has a consistent frustration for users. Such user interfaces cannot reveal which nodes essentially reference a given node. This regularly leads to a large amount of effort being needed to track down the references by hand.
The frustration similarly has only grown in significance as time has passed. Today there is a major effort underway by providers of creative content such as pictures, music, motion videos, etc. to uphold copyright protection. This has lead to the development of copyright signature embedding mechanisms for visual data, such as still frames. Determining if a node of content has been essentially incorporated into another content becomes the task of finding the copyright signature. The task of automatically searching a collection of nodes (perhaps distributed across a directory structure or across a network) becomes that much more significant.
Note again that the paradigm of a directory tree structure runs counter to what these users are trying to do. These essentially referenced files effectively create cycles in the file system graph from the user's standpoint. These operating systems (UNIX, MSDOS-Windows and MacOS) teach away from these cyclic graph structures.
Essential references based upon “essentially being contained”, open the door to the user thinking in terms of hypergraphs, where the essentially containing files represent the hyper-arcs and the points of the hypergraph are the files essentially referenced. Note that this is again something these very common operating systems do not conceptually permit.